The present invention relates to a method and a system for generating and/or verifying a digital signature by using a public key encryption method for securing the security in a computer network.
The digital signature technology for imparting electric documents or the like for electronic comments or transactions with a function equivalent to that of a conventional seal (hanko in Japanese) promises high efficiency utilization of computer-network system. However, with the conventional electronic mail encryption technology (also known as Privacy Enhanced Mail or PEM in abbreviation), it is impossible to process more than one digital signature for a single enhanced mail. In this conjunction, in the electronic commerce fields, it is expected in the not-so-distant future that the electronic document such as message and the like affixed with a number of digital signatures including not only the digital signature of a purchaser but also those of a distributor, salesman and/or monetary business-man will be handled. Under the circumstances, there arises a demand for the multiple digital signature technology which allows the electronic documents affixed with a plurality of digital signatures to be processed. In this conjunction, it is noted that a person receiving an electronic document affixed with a plurality of digital signatures will be forced to verify the authenticity of plural or N digital signatures written by other persons before writing or generating his or her own single digital signature. Thus, in order to enhance the availability of the digital signature facility in the computer network system, it will be required to increase the speed for verification of the plural (N) digital signatures. Besides, it is conceivable that in the electronic commerces, there is a possibility that comments may be added by a plurality of persons in the course of processing the electronic document.
For having better understanding of the invention, description will first be made in some detail of the technical background of the invention. As a typical one of the digital signature techniques known heretofore, there may be mentioned the public-key cryptography elliptic curve system disclosed in J. Koeller, A. J. Menezes, M. Qu and S. A. Vanstone: xe2x80x9cStandard for RSA, Diffie-Hellman and Related Public-Key Cryptography Elliptic Curve Systems (Draft 8)xe2x80x9d in xe2x80x9cIEEE P1363 Standardxe2x80x9d published by the IEEE, May 3, 1996 and May 14, 1996, respectively.
FIG. 9 is a schematic diagram showing generally a configuration of a computer network system in which the techniques disclosed in the above-mentioned literatures are adopted.
Referring to FIG. 9, there are connected to a network 1001 a system manager""s computer 1002, a user A""s computer 1003 and a user B""s computer 1004 for mutual communication.
Operations of the individual units shown in FIG. 9 will be described below.
System Setup
The system manager""s computer 1002 is in charge of generating an elliptic curve (E) 1006. Subsequently, a base point (also referred to as the system key) (P) 1007 of the order (n) 1008 is generated and registered in a public file 1005.
Key Generation
A key generating function module 1011 incorporated in the user A""s computer 1003 is designed to execute the processing steps which will be mentioned below.
Step 1: In an interval [2, nxe2x88x922], an integer dA is selected at random as a private key.
Step 2: A key QA is computed in accordance with QA=dAP.
Step 3: The key (QA) 1015 is opened to the public as the public key. More specifically, the public key (QA) 1015 is transmitted together with the identifier name of the user A to the system manager""s computer 1002 via the network 1001, whereon the identifier name of the user A is written in the public file 1005 at a column 1009 for the user A""s name with the value of the public key (QA) 1015 being written in a column 1010 for the public key QA.
Step 4: In the user A""s computer 1003, the value of the private key (dA) 1014 is held as the private key of the user A.
Digital Signature Generation Process
A digital signature generating function module 1033 incorporated in the user A""s computer 1003 is designed to execute the processing steps mentioned below.
Step 1: Message (M) 1016 is received.
Step 2: Hash value e=H(M) is computed by using a hash function (H) 1028.
Step 3: Random number k is selected from the interval [2, nxe2x88x922] by using a random number generation function 1029.
Step 4: Point kP=(x, y) is computed by a so-called xe2x80x9cscalar multiplication on elliptic curve (E)xe2x80x9d 1030.
Step 5: A first tally r given by r=x+e (mod n) is determined in accordance with the modular computation xe2x80x9cr=x+e (mod n)xe2x80x9d 1031.
Step 6: A private key (dA) 1017 is inputted to modular computation process xe2x80x9cs=kxe2x88x92dAr (mod n)xe2x80x9d 1032 for thereby determining a second tally s (=kxe2x88x92dAr (mod n)).
Step 7: A message M 1016 and the digital signature (r, s) 1019 are sent to the user B""s computer 1004 via the network 1001.
As the parameters required for the computations performed by the digital signature generating function module 1033, the elliptic curve (E) 1006, the base point which may also be referred to system key (P) 1007 and the order (n) 1008 registered in the public file 1005 held by the system manager""s computer 1002 are referenced.
Digital Signature Verification Process
A digital signature verifying function module 1023 incorporated in the user B""s computer 1004 is designed to execute the processing steps mentioned below.
Step 1: The user A""s public key (QA) 1010 is fetched from the public file 1005 held by the system manager""s computer 1002 to be set as a public key (QA) 1020. Additionally, the base point (system key) (P) 1007 is fetched from the public file 1005 held by the system manager""s computer 1002 to be set as the base point (P) 1007B. Furthermore, the digital signature (r, s) 1019 sent from the user A""s computer 1003 is received to be set as a digital signature (r, s) 1021. Besides, the message (M) 1016 sent from the user A""s computer 1003 is received to be set as a message (M) 1022.
Step 2: The base point or system key (P) 1007B, the public key (QA) 1020, the digital signature (r, s) 1021 are inputted to the process xe2x80x9cscalar multiplication on elliptic curve (E)xe2x80x9d and xe2x80x9cadditionxe2x80x9d 1024 to thereby carry out the calculation xe2x80x9c(x, y)=sP+rQAxe2x80x9d.
Step 3: The message M 1022 is inputted into the hash function H 1025 to thereby compute the hash value e=H(M).
Step 4: Through the computation process xe2x80x9crxe2x80x2=x+e (mod n)xe2x80x9d 1026, a first tally xe2x80x9crxe2x80x2=x+e (mod n)xe2x80x9d is determined.
Step 5: When the decision xe2x80x9cr=rxe2x80x2?xe2x80x9d 1027 results in r=rxe2x80x2 or YES, data xe2x80x9cauthenticatedxe2x80x9d is outputted, and if otherwise, xe2x80x9cnot authenticatedxe2x80x9d is outputted.
As the parameters required for the computations performed by the digital signature verifying function module 1023, the elliptic curve (E) 1006, the base point or system key (P) 1007 and the order (n) 1008 as registered in the public file 1005 held by the system manager""s computer 1002 are referenced.
Through the processes described above, the digital signature (r, s) functions as an electronic seal (i.e., seal or xe2x80x9chankoxe2x80x9d impressed electronically by the user A for the message M). To say in another way, the user B can hold the set of the message M and the digital signature (r, s) as the evidence indicating that the message M is issued by the user A. Further, although the user B can recognize the authenticity of the set of the message M and the digital signature (r, s), the user B can not originally generate the set of the message M and the digital signature (r, s). For this reason, the user A can not negate later on the fact that the digital signature (r, s) has been generated by the user A.
However, the conventional system described above suffers the problems which will be elucidated below.
(1) Insufficient Proof for Security
In general, generation of a digital signature by a person having no private key provides a problem. If otherwise, the authenticity of the digital signature can not be ensured, degrading the creditability of the electronic commerce and rendering it impractical.
In the conventional system described above, it is required to provide that such tally combination (r, s) can not be generated which allows the output xe2x80x9cauthenticatedxe2x80x9d to be generated in the course of the digital signature verification processing without knowing the private key dA. However, the conventional system provides no proof to this end. Parenthetically, it should be mentioned that the problem mentioned above has been pointed out in conjunction with ElGamal signature technology on which the conventional system described above is based.
(2) Long bit length of the digital signature
Now, assuming that relevant parameters have respective bit lengths as follows:
(a) The bit length representing the order n of the base point P is ln bits (e.g. 160 bits).
(b) The bit length representing the output of the hash function H is lH bits (e.g. 160 bits).
(c) The bit length of the private key dA is ld bits (e.g. 160 bits).
The output value of the hash function H given by of 160 bits is considered as being necessary in view of the fact that the hash function H has a collision-free property. In this conjunction, it is contemplated with the phrase xe2x80x9ccollision-free propertyxe2x80x9d to mean that difficulty is encountered in finding two different input values which result in a same output value in view of the computational overhead. By way of example, in the case where the output value of a hash function H is 160 bits, it will be possible to find two different input values which results in a same output value by carrying out an attack method known as xe2x80x9cParadox of Birthdayxe2x80x9d a number of times on the order of 280 on an average, which is however difficult in view of the computational overhead.
Further, the bit length of 160 bits for the order n of the base point (system key) is considered as being necessary because of difficulty of solving the discrete logarithm problem relevant to the addition on the elliptic curve.
In this case, when the length of the tally r of the digital signature (r, s) is of ln bits with the length of the tally s being of ln bits, then the total bit number amounts to (ln+ln) bits (e.g. 320 bits).
(3) The length of the digital signature is determined in dependence on the length of the parameter n of the elliptic curve. Consequently, when the length of the parameter n is increased for ensuring the security of the digital signature more positively in the future, the length of the digital signature increases correspondingly. Parenthetically, in conjunction with RSA and EES, it is noted that the length of the parameter n is unavoidably increased because of enhancement of the decryption method and the computer performance promoted as a function of the time lapse. The same will also apply equally to the elliptical encryption in the future. To say in another way, it is expected that the length of the parameter n will necessarily increase as the decryption technology and the computer performance are enhanced as a function of time lapse. Such being the circumstances, it is desirable in conjunction with the elliptic encryption to realize the digital signature which does not depend on the length of the order n of the base point or system key P.
In the light of the state of the art described above, it is an object of the present invention to provide a digital signature generating and/or verifying method and system using a public key encryption scheme with high security as well as a recording medium for storing a program for carrying out the method.
Another object of the present invention is to provide a digital signature generating and/or verifying method and system using a public key encryption scheme, which allows the bit length of the digital signature to be shortened, and a recording medium for storing a program realizing the same.
Yet another object of the present invention is to provide a digital signature generating/verifying method and system which are based on the use of a public key encryption method in which the length of the digital signature is made to be independent of the length of the order of the base point, and a recording medium employed for storing a program realizing the same.
In view of the above and other objects which will become apparent as the description proceeds, there is provided according to a first generic aspect of the present invention a digital signature generating/verifying method of generating and/or verifying a digital signature authenticating electronically a signature affixed to a given document or message (M) by resorting to a public key encryption scheme. The digital signature generating/verifying method includes processing steps of determining for the given document or message (M) a hash value (e) satisfying a condition that e=H(M) by using a hash function (H), and determining for a numerical value (x) derived from translation of a random number a hash value (r) satisfying a condition that r=h(x) by using a hash function (h) whose output value is shorter than that of the first-mentioned hash function (H).
Further, according to another general aspect of the present invention, there is provided a digital signature generating and/or verifying method of generating or verifying a multiple digital signature authenticating electronically signatures affixed to document such as messages and/or comments (Mi) as created and/or added sequentially by N users i (where i=1, . . . , N) by using a public key encryption scheme. The digital signature generating/verifying method includes the steps of (a) determining for a given one of the messages (Mi) a hash value (ei) satisfying a condition that ei=H(Mi) by using a hash function (H), (b) determining for a numerical value (xi) obtained from translation of a random number a hash value (ri) satisfying a condition that ri=h(xi) by using a hash function (h) whose output value is shorter than that of the first-mentioned hash function (H) and (c) executing the above-mentioned steps (a) and (b) for each of the users i (where i=1, . . . , N).
According to another general aspect of the present invention, there is provided a digital signature generating/verifying system for generating a digital signature authenticating electronically a signature affixed to a given message (M) by resorting to a public key encryption scheme. The digital signature generating/verifying system is composed of a processing unit for determining for the message (M) a hash value (e) satisfying a condition that e=H(M) by using a hash function (H), a processing unit or module for determining for a numerical value (x) obtained from translation of a random number a hash value (r) satisfying a condition that r=h(x) by using a hash function (h) whose output value is shorter than that of the hash function (H).
Furthermore, according to another general aspect of the present invention, there is provided a digital signature generating and/or verifying system for generating and/or verifying a multiple digital signature authenticating electronically signatures affixed to document such as messages and/or comments (Mi) as created and/or added sequentially by N users i (where i=1, . . . , N) by resorting to the use of a public key encryption scheme, wherein the digital signature generating/verifying system includes a module for determining for a given one of the messages (Mi) a hash value (ei) satisfying a condition that ei=H(Mi) by using a hash function (H), a module for determining for a numerical value (xi) derived from translation of a random number a hash value (ri) satisfying a condition that ri=h(xi) by using a hash function (h) whose output value is shorter than that of the first-mentioned hash function (H), and a module for validating the above-mentioned modules for each of the users i (where i=1, . . . , N).
The above and other objects, features and attendant advantages of the present invention will more easily be understood by reading the following description of the preferred embodiments thereof taken, only by way of example, in conjunction with the accompanying drawings.